package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.*;

public class SlidingPuzzle {
    public int slidingPuzzle(int[][] board) {
        //1.制作映射表
        int[][] neighbor = new int[6][];
        neighbor[0] = new int[]{1,3};
        neighbor[1] = new int[]{0,2,4};
        neighbor[2] = new int[]{1,5};
        neighbor[3] = new int[]{0,4};
        neighbor[4] = new int[]{1,3,5};
        neighbor[5] = new int[]{2,4};
        int m =2,n=3;
        StringBuilder start = new StringBuilder();
        StringBuilder target = new StringBuilder("123450");
        //将2X3的数组转化为字符串
        for(int i = 0;i<m;i++){
            for(int j =0;j<n;j++){
                start.append(board[i][j]);
            }
        }
        /*BFS搜索*/
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(start.toString());
        visited.add(start.toString());
        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            for(int i =0;i<sz;i++){
                String head = q.poll();
                if(head.equals(target.toString())){
                    return step;
                }
                //找到数字索引0
                int idx = 0;
                for(;head.toString().charAt(idx)!='0';idx++);
                //将数字0和响铃的数字交换位置
                System.out.println(head);
                for(int adj:neighbor[idx]){
                    StringBuilder newBoard = new StringBuilder(head);
                    char ch = newBoard.charAt(adj);
                    newBoard.setCharAt(adj,newBoard.charAt(idx));
                    newBoard.setCharAt(idx,ch);
                    //防止走回头路
                    if(!visited.contains(newBoard.toString())){
                        q.offer(newBoard.toString());
                        visited.add(newBoard.toString());
                    }
                }
            }
            step++;
        }
        return -1;
    }

    @Test
    public void test(){
        System.out.println(slidingPuzzle(new int[][]{{1, 2, 3}, {5, 4, 0}}));
    }


}
